package com.cb2.algorithm.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <a href='https://leetcode.cn/problems/maximum-difference-between-node-and-ancestor'>节点与其祖先之间的最大差值(Maximum Difference Between Node and Ancestor)</a>
 * <p>给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
 *                              8
 *                            /   \
 *                          3      10
 *                        /  \        \
 *                      1     6        14
 *                           /  \     /
 *                         4     7   13
 *      输出：7
 *      解释：
 *          我们有大量的节点与其祖先的差值，其中一些如下：
 *          |8 - 3| = 5
 *          |3 - 7| = 4
 *          |8 - 1| = 7
 *          |10 - 13| = 3
 * 在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。
 *
 * 示例 2：
 *      输入：root = [1,null,2,null,0,3]
 *      输出：3
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>树中的节点数在 2 到 5000 之间。</li>
 *      <li>0 <= Node.val <= 10^5</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/22 14:35
 */
public class LC1026MaximumDifferenceBetweenNodeAndAncestor_M {
    static class Solution {
        public int maxAncestorDiff(TreeNode root) {
            return dfs(root, root.val, root.val);
        }

        private int dfs(TreeNode node, int min, int max) {
            if (node == null) {
                return 0;
            }
            min = Math.min(min, node.val);
            max = Math.max(max, node.val);
            // 叶子节点直接返回当前路径的最大差值
            if (node.left == null && node.right == null) {
                return max - min;
            }
            // 非叶子节点递归计算子树并取最大值
            return Math.max(dfs(node.left, min, max), dfs(node.right, min, max));
        }


        public int iterator(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int maxDiff = 0;
            Deque<TreeNode> nodeStack = new ArrayDeque<>();
            Deque<Integer> minStack = new ArrayDeque<>();
            Deque<Integer> maxStack = new ArrayDeque<>();

            nodeStack.push(root);
            minStack.push(root.val);
            maxStack.push(root.val);

            while (!nodeStack.isEmpty()) {
                TreeNode currNode = nodeStack.pop();
                Integer currMin = minStack.pop();
                Integer currMax = maxStack.pop();
                if (currNode.left == null && currNode.right == null) {
                    maxDiff = Math.max(maxDiff, currMax - currMin);
                }

                if (currNode.right != null) {
                    nodeStack.push(currNode.right);
                    minStack.push(Math.min(currMin, currNode.right.val));
                    maxStack.push(Math.max(currMax, currNode.right.val));
                }

                if (currNode.left != null) {
                    nodeStack.push(currNode.left);
                    minStack.push(Math.min(currMin, currNode.left.val));
                    maxStack.push(Math.max(currMax, currNode.left.val));
                }
            }
            return maxDiff;
        }
    }
}